package com.lfg.leetcode.leetcode100;


import java.util.*;

public class No127ladderLength {

    public static void main(String[] args) {
//        List<String> list = new ArrayList<>(Arrays.asList("hot,dot,dog,lot,log,cog".split(",")));
        List<String> list = new ArrayList<>(Arrays.asList("hot,dot,dog,lot,log,cog".split(",")));
        int ret = ladderLength("hit", "cog", list);
        System.out.println("[" + ret + "]");
    }


    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> ret = new ArrayList<>();
        if (!wordList.contains(endWord)) {
            return ret.size();
        }
        wordList.add(beginWord);
        int length = wordList.size();
        Map<String, Set<String>> data = new HashMap<>(length);
        Set<String> endSet = new HashSet<>(length);
        endSet.add(endWord);
        return BFS(data, beginWord, endSet, wordList, 1);
    }

    public static int BFS(Map<String, Set<String>> data, String beginWord, Set<String> endSet, List<String> wordList, int length) {
        Set<String> nextSet = new HashSet<>(wordList.size());
        wordList.removeAll(endSet);
        for (Iterator<String> iter = endSet.iterator(); iter.hasNext(); ) {
            String endWord = iter.next();
            for (String str : wordList) {
                if (checkDifferent(endWord, str)) {
                    if (beginWord.equals(str)) {
                        return length + 1;
                    }
                    Set<String> set = data.computeIfAbsent(str, k -> new HashSet<>(wordList.size()));
                    set.add(endWord);
                    nextSet.add(str);
                }
            }
        }
        if (wordList.size() == 0 || nextSet.size() == 0) {
            return 0;
        }
        return BFS(data, beginWord, nextSet, wordList, length + 1);
    }


    public static boolean checkDifferent(String ori, String dest) {
        int diff = 0;
        for (int i = ori.length() - 1; i >= 0; i--) {
            if (ori.charAt(i) != dest.charAt(i)) {
                diff++;
            }
        }
        if (diff == 1) {
            return true;
        }
        return false;
    }

}
